package com.demo.java.OD401_450.OD450;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【堆内存申请(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146332006
 */
public class OdMain {
    // 定义内存块类，用于表示已分配的内存块
    static class MemoryBlock implements Comparable<MemoryBlock> {
        private final int offset;  // 内存块的偏移量
        private final int size;    // 内存块的大小

        public MemoryBlock(int offset, int size) {
            this.offset = offset;
            this.size = size;
        }

        public int getOffset() {
            return offset;
        }

        public int getSize() {
            return size;
        }

        // 根据偏移量比较内存块，用于排序
        @Override
        public int compareTo(MemoryBlock other) {
            return Integer.compare(this.offset, other.offset);
        }
    }

    // 分配内存的方法
    public static int allocateMemory(int requestedSize, List<MemoryBlock> allocatedMemory) {
        Collections.sort(allocatedMemory);  // 按偏移地址排序

        // 检查第一个内存块之前的空闲空间
        if (allocatedMemory.isEmpty()) {
            return 0;  // 如果没有已分配的内存，直接返回起始位置 0
        }

        // 遍历已分配内存块，查找空闲空间
        for (int i = 0; i < allocatedMemory.size() - 1; i++) {
            int startOffset = allocatedMemory.get(i).getOffset() + allocatedMemory.get(i).getSize();
            int endOffset = allocatedMemory.get(i + 1).getOffset();

            // 判断当前空闲空间是否足够
            if (endOffset - startOffset >= requestedSize) {
                return startOffset;  // 返回空闲空间的起始地址
            }
        }

        // 检查最后一个内存块之后的空闲空间
        int lastAllocationEnd = allocatedMemory.get(allocatedMemory.size() - 1).getOffset() +
                allocatedMemory.get(allocatedMemory.size() - 1).getSize();
        if (100 - lastAllocationEnd >= requestedSize) {
            return lastAllocationEnd;  // 返回空闲空间的起始地址
        }

        return -1;  // 无法找到足够的空间
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取请求的内存大小
        int requestedSize = Integer.parseInt(scanner.nextLine());  // 请求的内存大小
        List<MemoryBlock> allocatedMemory = new ArrayList<>();  // 存储已分配的内存块

        // 读取每个已分配的内存块
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (line.isEmpty()) {
                break;
            }

            String[] input = line.split(" ");
            try {
                int offset = Integer.parseInt(input[0]);
                int size = Integer.parseInt(input[1]);
                allocatedMemory.add(new MemoryBlock(offset, size));
            } catch (Exception e) {
                break;  // 输入格式错误或结束
            }
        }

        // 执行内存分配
        int result = allocateMemory(requestedSize, allocatedMemory);

        // 输出结果
        System.out.println(result);  // 输出分配的起始地址，或 -1

        scanner.close();
    }
}
